Scholar Hub/Chủ đề/#luồng cực đại/
Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (sourc...
Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (source) đến một đỉnh đích (sink) sao cho lưu lượng này là lớn nhất có thể.
Trong một mạng lưới, các đỉnh biểu thị vị trí và các cạnh biểu thị đường truyền thông giữa các vị trí đó. Mỗi cạnh có một số liệu gọi là khả năng chứa lưu lượng (capacity) - tức là lưu lượng tối đa có thể truyền qua cạnh đó.
Luồng cực đại tìm cách phân phối lưu lượng từ đỉnh nguồn đến đỉnh đích sao cho:
1. Lưu lượng trên mỗi cạnh không vượt quá khả năng chứa của cạnh đó.
2. Tổng lưu lượng đi qua mạng lưới là lớn nhất.
Để tìm luồng cực đại, các thuật toán như thuật toán Ford-Fulkerson hoặc thuật toán Edmonds-Karp được sử dụng. Các thuật toán này đều dựa trên khái niệm "đường cắt" (cut) trong đồ thị và sử dụng việc tăng cường đường đi (augmenting path) để tăng giá trị lưu lượng truyền qua mạng lưới.
Để hiểu chi tiết hơn về luồng cực đại, ta cần biết thêm một số khái niệm và thuật ngữ liên quan.
1. Đồ thị mạng (Network graph): Đồ thị mạng được sử dụng để biểu diễn một hệ thống hay mạng gồm các vị trí (đỉnh) và các đường truyền thông (cạnh) giữa chúng. Đồ thị mạng bao gồm một đỉnh nguồn (s) và một đỉnh đích (t), cùng với các đỉnh và cạnh khác.
2. Khả năng chứa lưu lượng (Capacity): Mỗi cạnh trong đồ thị mạng có một giá trị thể hiện lưu lượng tối đa mà cạnh đó có thể truyền qua. Đây là một giá trị không âm và có thể khác nhau cho từng cạnh.
3. Luồng (Flow): Một luồng trên đồ thị mạng là một phân phối của lưu lượng từ đỉnh nguồn đến đỉnh đích qua các cạnh. Luồng trên một cạnh phải thỏa mãn các ràng buộc sau:
- Không vượt quá khả năng chứa của cạnh: Lưu lượng trên mỗi cạnh phải nhỏ hơn hoặc bằng khả năng chứa của cạnh đó.
- Cân bằng luồng tại các đỉnh ngoại trừ đỉnh nguồn và đích: Tổng lưu lượng đến một đỉnh (trừ đỉnh nguồn và đích) phải bằng tổng lưu lượng ra khỏi đỉnh đó.
4. Luồng cực đại (Maximum Flow): Luồng cực đại trên một đồ thị mạng là luồng có tổng lưu lượng trên các cạnh là lớn nhất có thể. Điều này có nghĩa là không thể tăng giá trị của luồng bằng cách phân phối lưu lượng khác.
Thuật toán Ford-Fulkerson và Edmonds-Karp là hai phương pháp được sử dụng để tìm luồng cực đại trên đồ thị mạng. Cả hai thuật toán này đều dựa trên việc tìm đường đi từ đỉnh nguồn đến đỉnh đích (đường cắt) có thể cung cấp một lượng lưu lượng khả dụng tiếp theo để tăng giá trị của luồng. Thuật toán tiếp tục tìm kiếm đường đi này và tăng giá trị lưu lượng cho đến khi không còn đường đi nữa. Khi đó, luồng đã đạt đến cực đại.
Luồng cực đại có ứng dụng trong nhiều lĩnh vực như mạng máy tính, điều độ giao thông, lập lịch công việc, v.v.
Ước lượng dòng carbon bề mặt dựa trên bộ lọc Kalman chuyển đổi tổ hợp cục bộ với cửa sổ đồng hóa ngắn và cửa sổ quan sát dài: kiểm thử mô phỏng hệ thống quan sát trong GEOS-Chem 10.1 Dịch bởi AI Geoscientific Model Development - Tập 12 Số 7 - Trang 2899-2914
Tóm tắt. Chúng tôi đã phát triển một hệ thống đồng hóa dữ liệu carbon để ước lượng các dòng carbon bề mặt. Hệ thống này sử dụng bộ lọc Kalman chuyển đổi tổ hợp cục bộ (LETKF) và mô hình vận chuyển khí quyển GEOS-Chem được dẫn động bởi phân tích lại các trường khí tượng của MERRA-1 dựa trên mô hình Hệ thống Quan sát Trái Đất Goddard phiên bản 5 (GEOS-5). Hệ thống đồng hóa này lấy cảm hứng từ phương pháp của Kang và cộng sự (2011, 2012), những người đã ước tính dòng carbon bề mặt trong một thí nghiệm mô phỏng hệ thống quan sát (OSSE) như là các tham số thay đổi trong việc đồng hóa CO2 khí quyển, sử dụng cửa sổ đồng hóa ngắn 6 giờ. Họ đã bao gồm đồng hóa các biến khí tượng tiêu chuẩn, để tổ hợp mang lại một thước đo của độ không chắc chắn trong việc vận chuyển CO2. Sau khi giới thiệu các kỹ thuật mới như 'định vị biến động' và tăng trọng số quan sát gần bề mặt, họ đã đạt được các dòng carbon bề mặt chính xác ở độ phân giải điểm lưới. Chúng tôi đã phát triển một phiên bản mới của bộ lọc Kalman chuyển đổi tổ hợp cục bộ liên quan đến phương pháp 'ra-vào tại chỗ' (RIP) để tăng tốc giai đoạn tăng vòng của đồng hóa dữ liệu bộ lọc Kalman tổ hợp (EnKF) (Kalnay và Yang, 2010; Wang và cộng sự, 2013; Yang và cộng sự, 2012). Giống như RIP, hệ thống đồng hóa mới sử dụng thuật toán 'làm mịn không chi phí' cho LETKF (Kalnay và cộng sự, 2007b), cho phép dịch chuyển nghiệm của bộ lọc Kalman tiến hoặc lùi trong cửa sổ đồng hóa mà không tốn chi phí nào. Trong sơ đồ mới, một 'cửa sổ quan sát' dài (ví dụ, 7 ngày hoặc lâu hơn) được sử dụng để tạo ra tổ hợp LETKF sau 7 ngày. Sau đó, bộ làm mịn RIP được dùng để tạo ra phân tích cuối cùng chính xác trong 1 ngày. Cách tiếp cận mới này có lợi thế là dựa trên cửa sổ đồng hóa ngắn, điều này giúp nó chính xác hơn, và được tiếp xúc với những quan sát tương lai trong 7 ngày, điều này cải thiện phân tích và tăng tốc giai đoạn tăng vòng. Cửa sổ đồng hóa và quan sát sau đó được lùi lên trước 1 ngày, và quy trình này được lặp lại. Điều này giảm đáng kể lỗi phân tích, cho thấy rằng phương pháp đồng hóa mới được phát triển có thể được sử dụng với các mô hình hệ thống Trái Đất khác, đặc biệt là để tận dụng tốt hơn các quan sát kết hợp với các mô hình này.
#Kalman filter #carbon flux estimation #atmospheric transport model #GEOS-Chem #data assimilation #Earth system models #observing system simulation experiment #meteorological fields #ensemble Kalman filter #variable localization #carbon cycle.
Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộngĐồ thị và mạng mở rộng là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. [7]. Kết quả chính của bài báo là nghiên cứu thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng, sử dụng thuật toán tìm đường đi nhanh nhất trên mạng giao thông mở rộng [6]. Trên sơ sở bài toán đối ngẫu trong [7], tác giả xây dựng thuật toán đưa tỉ lệ hàm mục tiêu hai bài toán đối ngẫu này tiến đến 1, và từ đó suy ra luồng cực đại đồng thời chi phí cực tiểu. Đây là thuật toán tính gần đúng với tỉ lệ xấp xỉ là (1+w) với w dương nhỏ tùy ý. Bài báo phân tích, chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.
#đồ thị #mạng #luồng đa phương tiện #tối ưu #xấp xỉ
ĐÁNH GIÁ KẾT QUẢ PHẪU THUẬT NỘI SOI QUA ĐƯỜNG NIỆU ĐẠO CẮT PHÌ ĐẠI LÀNH TÍNH TUYẾN TIỀN LIỆT BẰNG ĐIỆN LƯỠNG CỰC Ở BỆNH NHÂN CÓ BỆNH LÝ TIM MẠCHMục tiêu: Đánh giá kết quả phẫu thuật nội soi qua đường niệu đạo cắt phì đại lành tính tuyến tiền liệt bằng điện lưỡng cực ở bệnh nhân có bệnh lý tim mạch. Đối tượng và phương pháp nghiên cứu: Nghiên cứu mô tả hồi tiến cứu trên 63 bệnh nhân bị u phì đại lành tính tuyến tiền liệt (UPĐLTTTL) có bệnh lý tim mạch kèm theo được điều trị bằng cắt đốt nội soi qua đường niệu đạo bằng điện lưỡng cựctại bệnh viện Đại Học Y Hà Nội từ tháng 01 năm 2019 đến tháng 5 năm 2021. Kết quả: NC hồi cứu 63 BN,độ tuổi trung bình là 73.5 ± 9.1, bệnh lý tim mạch đồng mắc: tăng huyết áp (THA) 73%, rối loạn nhịp tim 19.1%, bệnh mạch vành 9.5%, đặt máy tạo nhịp 6.4%, 8 bệnh nhân dùng thuốc chống đông. Điểm IPSS và QoL trước mổ 22.5 ± 3.8 và 4.6 ± 0.7, trọng lượng tuyến tiền liệt 68.3 ± 31.8g, phân suất tống máu (EF) trên siêu âm tim 68.9 ± 6.0%. Thời gian phẫu thuật 55.3 ± 21.4 phút, thời gian hậu phẫu 6.4 ± 2.0 ngày. Không gặp biến chứng trong mổ. Không có trường hợp nào đau thắt ngực, khó thở hay phải can thiệp tim mạch. Ba trường hợp biến chứng sau mổ: 2 chảy máu và 1 đau tức chân 2 bên, tất cả đều được điều trị nội ổn định. Tái khám 1 tháng không có trường hợp nào phải nhập viện điều trị về tim mạch, 1 trường hợp tử vong do bệnh phổi tắc nghẽn mạn tính. Kết luận: Phẫu thuật nội soi qua đường niệu đạo cắt phì đại tiền liệt tuyến bằng điện lưỡng cực (B-TURP) là phương pháp an toàn, hiệu quả trong điều trị phì đại lành tính tuyến tiền liệt trên nhóm bệnh nhân có bệnh lý tim mạch.
#Tăng sản lành tính tuyến tiền liệt #nội soi cắt tuyến tiền liệt qua niệu đạo bằng điện lưỡng cực #nội soi cắt tuyến tiền liệt qua niệu đạo trong nước muối (TURIS)
Thuật toán đường đi tăng luồng tìm luồng cực đại trên mạng hỗn hợp mở rộngĐồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Bài viết xây dựng mô hình mạng hỗn hợp mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả hơn. Kết quả chính của bài viết là thuật toán đường đi tăng luồng tìm luồng cực đại và định lý luồng cực đại lát cắt cực tiểu tương ứng trên mạng hỗn hợp mở rộng.
#đồ thị #mạng #luồng #luồng cực đại #thuật toán
Ước lượng kênh cực đại kỳ vọng cho các hệ thống OFDM có méo phi tuyếnBài báo đề xuất việc sử dụng bộ ước lượng kênh dựa trên thuật toán kỳ vọng-cực đại EM cho các hệ thống ghép kênh phân chia theo tần số trực giao OFDM có méo phi tuyến trên cơ sở xấp xỉ tuyến tính hóa sử dụng phân tích Bussgang mở rộng. Các kết quả phân tích và mô phỏng chứng minh rằng thuật toán đề xuất chỉ yêu cầu độ phức tạp tính vừa phải với số lần giải lặp nhỏ trong khi cải thiện rất đáng kể chất lượng ước lượng kênh so với các phương pháp ước lượng thông thường khác như sai số nhỏ nhất LSE hay sai số bình phương trung bình cực tiểu MMSE. Điều này cho phép thực hiện san bằng hiệu quả hơn và hệ thống do đó cải thiện đáng kể được tỉ lệ lỗi bit BER. Ngoài ra, bộ ước lượng EM-LSE có thể bảo đảm chất lượng ước lượng gần tương đương như bộ ước lượng EM-MMSE trong khi không yêu cầu thông tin đặc trưng thống kê của kênh pha-đinh, cho phép xây dựng bộ ước lượng mạnh trên cả kênh pha-đinh và kênh phi tuyến với độ phức tạp tính giảm thiểu.
#Nonlinear distortion; Channel estimation; Expectation maximization; OFDM.
Thuật toán đẩy luồng trước tìm luồng cực đại trên mạng hỗn hợp mở rộngĐồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Bài viết xây dựng mô hình mạng hỗn hợp mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả hơn. Kết quả chính của bài viết là thuật toán đẩy luồng trước tìm luồng cực đại và định lý luồng cực đại lát cắt cực tiểu tương ứng trên mạng hỗn hợp mở rộng.
#đồ thị #mạng #luồng #luồng cực đại #thuật toán
Thuật toán tìm luồng cực đại trên mạng giao thông mở rộngBài toán luồng cực đại trên mạng là một trong số những bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong các ngành như giao thông, truyền thông, công nghệ thông tin… Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong bài toán thực tế, trọng số tại mỗi đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi tại đỉnh đó. Chẳng hạn thời gian đi qua ngã tư trên mạng giao thông phụ thuộc vào hướng di chuyển của hàng hóa lưu thông: dòng rẽ phải, đi thẳng hay dòng rẽ trái và thậm chí có hướng bị cấm. Kết quả chính của bài báo là chúng tôi định nghĩa mô hình mạng giao thông mở rộng và xây dựng thuật toán tìm luồng cực đại trên mạng giao thông mở rộng.
#đồ thị #mạng #luồng #luồng cực đại #thuật toán
Điều kiện nối lưới cho nguồn điện mặt trời kết hợp với tuabin gió sử dụng giải thuật hệ bám điểm công suất cực đạiNghiên cứu sử dụng và khai thác hiệu quả nguồn điện mặt trời cũng như nguồn năng lượng gió để phát điện có ý nghĩa thiết thực đến việc giảm biến đổi khí hậu. Công nghệ hiện nay đang sử dụng các tế bào quang điện, để đảm bảo các tế bào quang điện luôn hoạt động ở công suất tối đa, hệ thống phải vận hành quanh điểm cực đại MPP. Việc kết hợp nguồn điện mặt trời với tuabin gió nối lưới, ưu điểm của hệ thống là sự chủ động được nguồn đầu vào. kết quả mô phỏng hệ thống điều khiển nối lưới cho nguồn pin mặt trời kết hợp với tuabin gió sử dụng phương pháp giải thuật hệ bám điểm công suất cực đại nhằm duy trì công suất phát tối đa của hệ thống bất chấp tải nối với hệ thống.
#Năng lượng tái tạo #pin mặt trời #tuabin gió #mặt trời nối lưới kết hợp với tuabin gió #hệ bám điểm công suất cực đại
